1. Field of the Invention
The invention pertains generally to computer systems. In particular, it pertains to avoiding deadlocks and livelocks in the dispatching and execution of bus transactions.
2. Description of the Related Art
In a continuing attempt to increase performance, many computer systems send bus transactions to a centralized input/output (I/O) controller, which uses multiple queues to dispatch each transaction to one of several different interfaces in the system, and which coordinates execution of various stages of the transaction.
FIG. 1 shows a portion of a conventional computer system containing such a centralized I/O controller 10, which controls the transfer of commands and data between processors 11, 12, graphics controller 13, memory controller 14, and peripheral bus controller 15. Each is connected to I/O controller 10 over a separate interface 21, 23, 24 and 25, respectively, each of which may be a bus.
FIG. 2 shows a more detailed view of I/O controller 10. A request from one of the CPU's 11, 12 to initiate a transaction is decoded by request decoder 111, which loads the request into In-Order Queue (IOQ) 112. IOQ 112 keeps the various phases of multiple transactions executing in the correct order, so that a given phase of a subsequent transaction will not be executed before the same phase of a preceding transaction. This is done by placing the request for the transaction into dispatch queue 113 and response queue 115, and for memory requests, into snoop queue 117 and snoop response queue 119. Although shown and discussed as four separate queues, these may actually be a single queue with four separate pointers indicating which location is considered to be the exit of the queue for each function.
When an indicator exits dispatch queue 113, it triggers dispatcher 114 to send the transaction to the correct interface 23, 24 or 25, through the associated command queue 130, 140, or 150, which queues up the transaction before it is presented to the respective interface. The transactions are “drained” from the command queues as the transactions are serviced by the receiving circuitry. When the target device responds, that response clears the associated request from the exit of response queue 115. If the request is to a memory system with cache, a snoop function and its response are also processed through queues 117, 119. Thus a transaction is completed only when the relevant request has been cleared from all queues in IOQ 112.
Memory transactions through queue 150 are typically guaranteed to complete within a specified time, and occupy processor bus 21 until the transaction is complete. However, transactions through downstream queues 130 and 140 (“downstream transactions”) have no guaranteed completion time, and time to complete can vary greatly. Since a target device may not always be ready to accept a command, alternative responses are available to prevent this condition from clogging up the queues. A retry response is a response from the I/O controller to the requestor that tells the requester to abort the request and try again later. This response clears that particular request from all queues in IOQ 112. When the request is retried at a later time, it enters IOQ 112 as a new request. A delayed transaction response includes a retry response, but the I/O controller 10 and the target interface also commit resources to the eventual retry, thus blocking those resources from other transactions and potentially forcing those other transactions to be reattempted. Only one transaction may be delayed at a time. A deferred response does not require a reattempt by the initiator—the I/O controller notifies the initiator that the target device will provide the requested data when it is ready, and the I/O controller will pass the data on to the initiator using a special transaction called a deferred reply. Although the transaction is complete when the request is deferred, the operation continues until the deferred reply, and various resources may remain committed until the deferred reply. In all these cases, the request is cleared from the queues in IOQ 112 when the retry/delay/defer status is created by the response from the I/O controller to the requestor. A request can be initially assigned an identifier, so that if it is reattempted with the same identifier, all affected devices can correlate the reattempt with the original request.
The interactive nature of the various queues and associated resources can cause both deadlocks and livelocks to occur, based on conflicting resource dependencies. As applied to the queue structure, a deadlock occurs when the output of two or more queues cannot be cleared because the data to initiate a clearing action in each is blocked within the other queue. A livelock occurs when a requested transaction cannot make progress in one queue because it depends on another queue which, although moving, is always full and thereby repeatedly forcing some type of reattempt. In brief, a livelock creates an ongoing bottleneck in the system, which may eventually go away in normal operation after an unacceptably long time, while a deadlock causes a blockage in the system that will not go away without some type of overt corrective action.
Some deadlocks and livelocks are generic to a system and can be avoided through proper overall system design. Others are only seen during specific, unusual circumstances and must be addressed with a customized solution on a case-by-case basis.